package leetcode;

/*
637. 二叉树的层平均值
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
示例 1：
输入：
    3
   / \
  9  20
    /  \
   15   7
输出：[3, 14.5, 11]
解释：
第 0 层的平均值是 3 ,  第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。
*/

import java.util.ArrayList;
import java.util.List;

public class problems_637 {
    public static void main(String[] args) {
        TreeNode A1 = new TreeNode(2147483647);
        TreeNode A2 = new TreeNode(2147483647);
        TreeNode A3 = new TreeNode(2147483647);
        TreeNode A4 = new TreeNode(15);
        TreeNode A5 = new TreeNode(7);
        A1.left = A2;
        A1.right = A3;
//        A3.left = A4;
//        A3.right = A5;
        System.out.println(new Solution().averageOfLevels(A1));
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    static class Solution {
        public List<Double> averageOfLevels(TreeNode root) {
            List<TreeNode> floor = new ArrayList<>();
            floor.add(root);
            //
            List<Double> ret = new ArrayList<>();
            while (!floor.isEmpty()) {
                Long sum = 0L;
                List<TreeNode> list = new ArrayList<>();
                for (int i = 0; i < floor.size(); i++) {
                    sum += floor.get(i).val;
                    if (null != floor.get(i).left) list.add(floor.get(i).left);
                    if (null != floor.get(i).right) list.add(floor.get(i).right);
                }
                ret.add((double) sum / floor.size());
                floor = list;
            }
            return ret;
        }
    }
}